Vés al contingut

Bucle (teoria de grafs)

De la Viquipèdia, l'enciclopèdia lliure
Un graf amb un bucle en el vèrtex 1.

En teoria de grafs, un bucle o loop és una aresta que connecta un vèrtex amb si mateix. Un graf simple no té bucles.

Depenent del context, un graf o multigraf pot estar definit o no per permetre-hi la presència de bucles.

Graus

[modifica]

Per a un graf no dirigit, el grau d'un vèrtex és igual al nombre de vèrtexs adjacents. No obstant això, si un vèrtex té un bucle, hem de sumar 2 al grau. Això és perquè cada connexió de l'aresta del bucle compta com el seu propi vèrtex adjacent, o en altres paraules, un vèrtex amb un bucle es veu a si mateix com un node adjacent des dels dos extrems de l'aresta.

Per a un graf dirigit, un bucle suma 1 al grau d'entrada i 1 al grau de sortida.

Bibliografia

[modifica]
  • Balakrishnan, V. K.; Graph Theory , McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4.
  • Bollobas, Bela; Modern Graph Theory , Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
  • Diestel, Reinhard; Graph Theory , Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
  • Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications , CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
  • Gross, Jonathon L, and Yellen, Jay; (eds); Handbook of Graph Theory . CRC (December 29, 2003). ISBN 1-58488-090-2.
  • ZWILLING, Daniel; CRC Standard Mathematical Tables and Formuleu , Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.